/*
题目: 将区间分为最少组数
给你一个二维整数数组 intervals ，其中 intervals[i] = [lefti, righti] 表示 闭 区间 [lefti, righti] 。

你需要将 intervals 划分为一个或者多个区间 组 ，每个区间 只 属于一个组，且同一个组中任意两个区间 不相交 。

请你返回 最少 需要划分成多少个组。

如果两个区间覆盖的范围有重叠（即至少有一个公共数字），那么我们称这两个区间是 相交 的。比方说区间 [1, 5] 和 [5, 8] 相交。

https://leetcode.cn/problems/divide-intervals-into-minimum-number-of-groups
 */
public class MinGroup {
    public int minGroups(int[][] intervals) {
        // 根据开始时间排序
        Arrays.sort(intervals, new Comparator<int[]> () {
            public int compare(int[] o1, int[] o2) {
                if (o1[1] != o2[1]) {
                    return o1[0] - o2[0];
                }
                return o1[1] - o2[1];
            }
        });
        int n  = intervals.length;

        // 堆中的一个元素就是一组d
        PriorityQueue<Integer> heap = new PriorityQueue<> ();
        heap.offer(intervals[0][1]);
        for (int i = 1; i < n; i ++) {
            if (intervals[i][0] > heap.peek()) {
                heap.poll();
            }
            heap.offer(intervals[i][1]);
        }
        return heap.size();
    }
}
/*
贪心：把所有区间按照左端点排序，然后遍历区间。对于当前区间的左端点，如果能找到一个最右端点都触碰不到它的组，就将这个区间并入那个组，
然后更新这个组的最右端点；否则就需要开一个新的区间。因此，我们需要用小根堆来维护之前每组区间的最右端点，最后堆中元素的数目就是最小组数。
 */
